#ifndef DAG_H
#define DAG_H

#include <list>
#include <vector>
#include <algorithm>
#include <tr1/unordered_map>

template <typename T> class Dag {
  private:
    class Node {
      friend class Dag<T>; //we show Node's private methods and fields to this class
      T state; // game state
      int counter; // how many nodes point to this node
      typename T::value_type value; // value_type field specified state class
      typename std::list<std::pair<typename T::move_type, Node*> > children; // it remembers the children and moves leading into them, we want to return move, not the game state

      Node(T const& s) : state(s), counter(0), value(s)
      {
      }
    };

    std::tr1::unordered_map<T, Node*> nodes; // hash table
    // I heard that Deep Blue, program that won with Kasparow, didn't care about collision in hash table, maybe it would be payable to do so, I don't know really
    Node* root;

    void erase(Node* n)
    {
      nodes.erase(n->state);
      typename std::list<std::pair<typename T::move_type, Node*> >::iterator it = n->children.begin();
      while (it != n->children.end()) {
        Node* tmp = it->second;
//        tmp->parents.remove(n);
        tmp->counter--;
        if (tmp->counter == 0) {
          erase(tmp);
        }
        it++;
      }
      delete n;
    }

    Node* get(T const& v) // returns exissting node or creates a new one
    {
      typename std::tr1::unordered_map<T, Node*>::iterator it = nodes.find(v); // find returns end if it hasn't found
      if (it != nodes.end()) return it->second;
      Node* n = new Node(v);
      nodes[v] = n; //we throw it into nodes
      return n;
    }

    static bool child_less(std::pair<typename T::move_type, Node*> const& c1, std::pair<typename T::move_type, Node*> const& c2)
    {
      return c1.second->value < c2.second->value;
    }


  public:
    Dag(T const& state)
    {
      root = get(state);
      root->counter++; // (paranoia)
    }

    bool has_children(T const& state)
    {
      Node* n = get(state);

      return !n->children.empty();
    }
    
    std::list<T> get_children(T const& state)
    {
      Node* n = get(state);
      typename std::list<std::pair<typename T::move_type, Node*> >::iterator it = n->children.begin();
      std::list<T> res;

      while (it != n->children.end()) {
	res.push_back(it->second->state);
	it++;
      }

      return res;
    }
    
    //when we call this function it may change values of many nodes in DAG
    void expand(T const& state)
    {
      typename std::tr1::unordered_map<T, Node*>::iterator it = nodes.find(state);
      if (it == nodes.end()) return; //I would throw std::logic_error
      Node* n = it->second; //read sth more
      if (!n->children.empty()) return;
      std::vector<typename T::move_type> moves = state.generateAllMoves();
      if (moves.empty()) return;
      typename std::vector<typename T::move_type>::iterator iti = moves.begin();
      while (iti != moves.end()) {
        Node* n2 = get(state.applyMove(*iti)); // this function - makes move
        n->children.push_back(std::make_pair(*iti, n2));;
        n2->counter++;
        iti++;
      }
//      update_value(n);
    }

    void update_value(T const& state)
    {
      Node* n = get(state);
      
      if (n->children.empty()) return;
      n->value = -std::min_element(n->children.begin(), n->children.end(), child_less)->second->value; // minus because we want to pick maximum value for us which is less value for our opponent - 
    }

    T const& commit(typename T::move_type const& move) // makes new root and removes oldone and everything else that's useless now
    {
      Node* new_root = get(root->state.applyMove(move));
      new_root->counter++;
      root->counter--;
      if (root->counter == 0) erase(root);
      root = new_root;
      return root->state;
    }

    typename T::move_type const& best_move(T const& state)
    {
      Node* node = get(state);
      // position value means value for player whose turn is
      return std::min_element(node->children.begin(), node->children.end(), child_less)->first;
    }

};

#endif
